// 2025/3/17
// https://leetcode.cn/problems/course-schedule/solutions/359392/ke-cheng-biao-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
// 课程表

class Solution {
    private:
        vector<vector<int>> edges;
        vector<int> indeg;
    
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            edges.resize(numCourses);
            indeg.resize(numCourses);
            for (const auto& info: prerequisites) {
                edges[info[1]].push_back(info[0]);
                ++indeg[info[0]];
            }
    
            queue<int> q;
            for (int i = 0; i < numCourses; ++i) {
                if (indeg[i] == 0) {
                    q.push(i);
                }
            }
    
            int visited = 0;
            while (!q.empty()) {
                ++visited;
                int u = q.front();
                q.pop();
                for (int v: edges[u]) {
                    --indeg[v];
                    if (indeg[v] == 0) {
                        q.push(v);
                    }
                }
            }
    
            return visited == numCourses;
        }
    };
    
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/course-schedule/solutions/359392/ke-cheng-biao-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


    class Solution {
        private:
            vector<vector<int>> edges;
            vector<int> visited;
            bool valid = true;
        
            void dfs(int n)
            {
                visited[n] = 1;
                for(auto& e : edges[n])
                {
                    if(visited[e] == 0)
                    {
                        dfs(e);
                        if(!valid) return;
                    }
                    else if(visited[e] == 1)
                    {
                        valid = false;
                        return;
                    }
                }
                visited[n] = 2;
            }
        
        public:
            bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
                edges.resize(numCourses);
                visited.resize(numCourses);
                for(const auto& v : prerequisites)
                {
                    edges[v[1]].push_back(v[0]);
                }
        
                for(int i = 0; i < numCourses && valid; i++)
                {
                    if(visited[i] == 0)
                        dfs(i);
                }
        
                return valid;
            }
        };